//class Solution {
//public:
//    vector<int> preorderTraversal(TreeNode* root) {
//        vector<int> v;
//        stack<TreeNode*> s;
//        if (root == nullptr) {
//            return v;
//        }
//        s.push(root);
//        while (!s.empty()) {
//            while (root) {
//                s.push(root);
//                v.push_back(root->val);
//                root = root->left;
//            }
//            TreeNode* cur = s.top();
//            s.pop();
//            root = cur->right;
//        }
//        return v;
//    }
//};

//struct TreeNode {
//	int val;
//	TreeNode* left;
//	TreeNode* right;
//	TreeNode() 
//		: val(0), left(nullptr), right(nullptr)
//	{	}
//	TreeNode(int x)
//		: val(x), left(nullptr), right(nullptr)		
//	{	}
//	TreeNode(int x, TreeNode* left, TreeNode* right) 
//		: val(x), left(left), right(right)	
//	{	}
//}
//class Solution {
//public:
//    vector<int> inorderTraversal(TreeNode* root) {
//        vector<int> v;
//        stack<TreeNode*> s;
//        if (root == nullptr) {
//            return v;
//        }
//        while (root || !s.empty()) {
//            while (root) {
//                s.push(root);
//                root = root->left;
//            }
//            TreeNode* cur = s.top();
//            v.push_back(cur->val);
//            s.pop();
//            root = cur->right;
//        }
//        return v;
//    }
//};